Post 50 trainingWeek

Veröffentlicht am | Edited on

序

未来七天持续更新培训情况，主要以题解为主，有些培训的心得也会说说？

Day1

考试混了个勉强过得去的名次qwq，话说来这的大部分都很菜啊。

其实今天题挺简单的

下午没睡好觉状态不好，结果也没有完全都听清楚，尤其是最大匹配必须边和可行边以及一些网络流的题，名字到是记住了：动态加边，动态加层。。。

然后上午T3现在还不会？？？？
怎么他们全都AK了啊qwq

Day2

map比我想象的慢多了，而且今天变成了暴力欢乐赛2333.

Au wzx又嘲讽我！！！
然后还有个神仙切了T3

然后我好像挂了不少分其实还行。

Day1正式

先放一下题目。

T1

本质上是Haffman树。

我们可以这么想，第一维表示像左边合并到的位置，第二维表示有几颗树，每次要么合并一半的树，要么添加一个点。

这样就变成了合并果子。

关于向上取整导致的多出来的那棵树，我和成爷讨论了一下应该是因为费用提前计算了一次？

不管了玄学题

T2

据说是一道AC自动机套路题。。
其实解法不是很难啦，就是做的题目类型太少了？？
我这道题一分也没有
先说一下50分的KMP做法
设$f{i,j,k,p}$表示走到第$(i,j)$个位置，第一个串匹配到$k$位置，第二个串匹配到$p$位置，起始状态是$f{0,0,0,0}$，最终状态是$f{n,m,l1,l2}$，dp顺序就是从小到大枚举。处理出两个串的next数
组后就可以暴力枚举转移了。
我写了一发输出0，貌似细节也挺多的。
正解是AC自动机，对两个串建立AC自动机后可以利用自动机转移，假如不加trie图优化的话大概麻烦一点。
设$f{i,j,k,0/1/2/3}$表示走到位置$(i,j)$，节点为$k$，已经匹配了模式串的状态压缩为最后一维。
转移的时候枚举下一步是什么和节点的对应儿子转移（不加Trie图好像挺麻烦？）

最后的答案就是$\sum{i=1}^{tot}f{n,m,i,3}$ , tot是自动机的节点数。

T3

最神仙的题，一道网络流。
好像要用到DAG覆盖的一些知识
问了问shzr大佬这道题的初步做法，其实就是最小路径覆盖n个点。

然后要赶紧学网络流扩展了（都怪那天中午没睡觉结果还感冒不清结果就没有听好最重要的一节课qwq）。

放这天的ppt

Day2正式

先放两天讲课的ppt

又是垃圾题目，甚至有原题，T3思路神仙，T2十分难写，T1暴力碾标算。

正式题解：

T1

一道真正的神仙题。

不过只要暴力就可以通过。。。

只需要稍微优化一下枚举范围，最大范围到[n/2]即可。

正解：挖掘性质。

排列意味着什么？$n$以内的每个数必定会出现！

然后就可以神仙了：考虑从左往右扫描每个点，在经常想象的权值数轴上，如果我们发现当前点和前面一个点已经存在，关于这个点对称的点不存在，那么等差子序列自然是一定存在的了。

然后我们需要一个支持更新Hash值和查询Hash值的数据结构，可以用线段树完成。

时间复杂度$O(nlogn)$

T2 , T3还是看题解吧。

Day3

SDOI2017的Day2原题。

T1

一道挺简单的费用流。

首先我们二分比值，把问题转化为判定当前答案。

问题转化为选出$n$对人，每个人只能用一次（类似匹配），要求$\sum_{i=1}^{n} a_i-kb_i$大于0.

最大费用最大流即可。

也算切了

T2暂时不会。

T3一看是线段树，不过并不想写。

ps：据说ATP在这场一轮中SD king得到了540分qwq。

下午讲的阿狸的打字机，品酒大会，优秀的拆分都好神仙啊，AC自动机的题目好像比SAM还简单，那我岂不是什么都不会啊qwq。算法泛学就此结束嘤嘤嘤。（只会胡乱看看模板题）

wzx什么都会

然后发现关于SA的$h$数组的性质$h[rk[i]] >= h[rk[i-1]] - 1$这条性质的证明非常简单，这也是线性求$h$的理论依据。

马上去完善SA的笔记qwq

左偏树要是想查找元素的堆顶必须使用并查集石锤了。

现在还是不会写
电不多了，回宾馆了。

然后补完了关于那个重要性质的证明.课上那个人显然漏掉了$h[rk[i-1]]$为0的情况，$k+1$可以在任何位置，不过那样是平凡情况，并不影响正确性或时间复杂度。

所以我们可以线性推出height数组，进而完成更多高端操作。

day4

不知道为啥感冒突然变得严重，结果上午只好滚粗回宾馆。

然后开始学习（颓废）

先放一下今天的题目吧qwq。

然后放一下今天的课件，lyd的课emmmmm，干货挺多的。

感冒好严重啊，加上下午干烧了好几个小时啥也没听进去，晚上实在GG了就去不了了，课也听不了了。。。。。

培训最重要的内容最终没有学好，呵呵。

又看到群里说什么OI被教育部取消了什么的。。。

感觉现在心情真是无比的低落，曾经我因为语文sb感觉高考sb来学OI（本来想学其他竞赛的。。），现在才发现除了语文可能OI是我最不擅长的了。

好像没有什么继续下去的必要了。

培训回去之后也就安心学文化课了，反正分班成绩已经定了，没法更好也没法更坏，卡线进吧。

继续看神仙题题解。。。。

智商太低都切不动

看了道luogu P1411第一反应树上背包，然后欣喜的发现需要高精度。

sb luogu。

day5

那个sb教室的环境简直让人无法待下去（对于感冒严重的我来说。。）

然后又提前一个小时滚了回来。

然后就喝喝水吃吃药就开始看我不会的各种题，顺便挂上windows易升。

然后发现该吃饭了，准备去吃碗馄饨，然后回来下载完新版win10更新。

发现我的企业版居然能升级哎，真是好运。

然后好像显卡就没毛病了，这台电脑又正常了一点。

感觉还是发烧，就又咕咕咕了晚上，反正毕克讲的也听不懂。

准备写道难一点的思维题来恢复一下233.

先放一下今天的题目。

题解

我自己口胡的，不确定对不对。

T1直接暴力卡常即可AC，正解大概是转一下然后二维树状数组。

T2是个sb线段树+扫描线。

T3不会，好像正解是线性递推的高效算法，就是那个Cayley-Hamilton定理+NTT优化多项式除法还有各种知识的东西。。

然后他今天没讲群伦。

然后放一下今天的培训内容，感觉又是什么都没学会。。好像还真不如在家里好好学，培训看来确实没什么卵用。。

准备收拾收拾早睡，假如明天上午不是很难受的话就好好写一次模拟题吧。

忽然看到关于fibonacci循环节的一篇严格证明（其实就我的水平也看不大懂），luogu有差不多的翻译

https://gradprogram.math.arizona.edu/~ura-reports/071/Campbell.Charles/Final.pdf

luogu由 EMT__Mashiro 写的题解还是很不错的，不过准备睡觉了qwq。

Day6

看上去题目应该挺有意思的。

不过毕克讲的确实很。。。。感觉跟听着玩一样，走马观灯的啥也没学会实际上。。。。。

干脆晚上不去了。。。。

顺便写一篇题解？

题目：

[SDOI2017]新生舞会

题目描述

学校组织了一次新生舞会，Cathy作为经验丰富的老学姐，负责为同学们安排舞伴。

有nn个男生和nn个女生参加舞会买一个男生和一个女生一起跳舞，互为舞伴。

Cathy收集了这些同学之间的关系，比如两个人之前认识没计算得出 a_{i,j}ai,j

Cathy还需要考虑两个人一起跳舞是否方便，比如身高体重差别会不会太大，计算得出 b_{i,j}bi,j，表示第i个男生和第j个女生一起跳舞时的不协调程度。

当然，还需要考虑很多其他问题。

Cathy想先用一个程序通过a{i,j}ai,j和b{i,j}bi,j求出一种方案，再手动对方案进行微调。

Cathy找到你，希望你帮她写那个程序。

一个方案中有n对舞伴，假设没对舞伴的喜悦程度分别是a’_1,a’_2,…,a’_na1′,a2′,…,an′，假设每对舞伴的不协调程度分别是b’_1,b’_2,…,b’_nb1′,b2′,…,bn′。令

C=\frac{a’_1+a’_2+…+a’_n}{b’_1+b’_2+…+b’_n}C=b1′+b2′+…+bn′a1′+a2′+…+an′

Cathy希望C值最大。

输入输出格式

输入格式：

第一行一个整数n。

接下来n行，每行n个整数，第i行第j个数表示a_{i,j}ai,j。

接下来n行，每行n个整数，第i行第j个数表示b_{i,j}bi,j。

输出格式：

一行一个数，表示C的最大值。四舍五入保留6位小数，选手输出的小数需要与标准输出相等。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
3
19 17 16
25 24 23
35 36 31
9 5 6
3 4 2
7 8 9

输出样例#1：

1
5.357143

说明

对于100%的数据，$1\le n\le 100,1\le a{i,j},b{i,j}<=10^4$

题解

考试的时候我随手爆切到了这道题。

一个非常显然的分数规划转判定。

判定只需要费用流。

考虑到男生女生只能配一个（不可以3p） ， 因此任意男女生连流量为1的边，然后费用是$A{i,j} - cur*B{i,j}$

跑一个最大费用最大流，最后一定满流不用管，只需要看看最大费用是否大于0即可。

时间复杂度无（雾

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 2005
#define INF 0x7fffffff
int head[205] , ct = 1, n , s , t , pre[205] , ep[205] , fw[205];
double a[101][101] , b[101][101] , d[205] , ans;
bool vis[205];
struct edge{
    int next , to , fw;
    double dis;
}e[35000];
struct queue
{
    int q[8005] , hd , tl;
    queue(){
        std::memset(q,0,sizeof(q));
        hd = 1 , tl = 0;
    }
    inline void clear(){
        hd = 1 , tl = 0;
    }
    inline void push(int x){
        q[++tl] = x;
    }
    inline void pop(){
        q[hd++] = 0;
    }
    inline int size(){
        return tl-hd+1;
    }
    inline int front(){
        return q[hd];
    }
}q;

inline void add(int x, int y , int fl , double dis)
{
    e[++ct] = (edge){head[x] , y , fl , dis};
    head[x] = ct;
}
inline int spfa()
{
    q.clear();
    for(int i = 1 ; i <= (n << 1) + 1; ++i)  d[i] = -INF , fw[i] = INF;
    q.push(s);
    vis[s] = true , d[s] = 0 , pre[t] = -1 , fw[s] = INF;
    for(int k ; q.size() ; q.pop())
    {
        k = q.front();
        vis[k] = false;
        for(int i = head[k] ; i ; i = e[i].next)
        {
            int v = e[i].to;
            if(d[k] + e[i].dis > d[v] && e[i].fw)
            {
                fw[v] = std::min(fw[k] , e[i].fw);
                d[v] = d[k] + e[i].dis;
                pre[v] = k;
                ep[v] = i;
                if(!vis[v])
                {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return pre[t];
}

inline double EK()
{
    double cost = 0;
    for( ; spfa() != -1 ; )
    {
        int k = t;
        cost += d[t] * fw[t];
    //	printf("ARGUMENT : %lf %d\n",d[t] , fw[t]);
        while(k != s)
        {
            e[ep[k]].fw -= fw[t] , e[ep[k]^1].fw += fw[t];
            k = pre[k];
        }
    }
//	printf("THE COST : %lf\n",cost);
    return cost;
}
void print(int x)
{
    for(int i = head[x] ; i ; i = e[i].next)
    {
        printf("%d -> %d %d %lf\n",x , e[i].to,e[i].fw , e[i].dis);
        if(e[i].fw) print(e[i].to);
    }
}
inline void build(double cur)
{
    std::memset(head,0,sizeof(head));
    ct = 1 ;
    s = 0 , t = (n << 1) + 1;
    for(int i = 1 ; i <= n ; ++i)
        add(s , i , 1 , 0) , add(i , s , 0 , 0);
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1; j <= n ; ++j)
            add(i , j + n , 1 , a[i][j] - cur * b[i][j]) , add(j + n , i , 0 , -(a[i][j] - cur * b[i][j]));
    for(int i = n + 1 ; i <= n << 1 ; ++i)
        add(i , t, 1 , 0) , add(t , i , 0 , 0);
//	print(s);
}

int main()
{
//	freopen("ball.in","r",stdin);
//	freopen("ball.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= n ; ++j)
            scanf("%lf",&a[i][j]);
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= n ; ++j)
            scanf("%lf",&b[i][j]);
    double l = 0 , r = 10000 , ran = 1e-7;
    if(n == 100) ran = 7e-6;
    while(r-l > ran)
    {
        double mid = (l + r) / 2;
        build(mid);
        if(EK() >= 0) l = mid;
        else r = mid;
    }
    printf("%.6lf",(l+r)/2);
}

还卡精度，垃圾。（Orz jzh qwq）

day7

感觉还行，切了T2后10点就滚回来了，因为我的水去了一个小时就没了。。。

回来颓废学习一下各种神仙线段树玩法。

徐明宽感觉好有气势啊，不愧是IOI rank2.

发现T2 fst了，果然是个假的算法，正解难度不低于NOI

T3好像是IOI难度的233.

我觉得还是有必要放一下题。

以及讲课内容。

然后今天的课件上的题目也很不错，貌似有3道是徐明宽的题（小Y原来是他

WC结束了，明年看看能不能去一次吧，不过愿望好像一点都不强烈了。

WC出成绩了，rqy第一唉，而且还是在出锅没拿到额外时间的情况下？

去看了看WC的课件，果然和我们这个培训水平差距悬殊。。。

除了xmk比WC的lecturer强以外，好像其他的也就一般吧。

xmk讲的真的挺好，也可能是我感冒稍微好点了？

emm差不多培训的都放上了吧（有漏的不管了好像只有毕克的课件忘了拷，一会补上qwq

唉，要是我能去WC多好（不过我们最高的都没去成

为了方便放下WC的各种神仙课件qwq（好像文件有点多了

暴力出奇迹，神奇指令集！

非常高端的生成函数，图论计数等等（学不会

具体数学选讲

量子计算！

良心的基础数论课件

神奇的可追溯数据结构

费用流相关

看上去非常厉害的一个东西

Lyndon Tree（很高端的样子

字符串前沿算法

题目选讲（据说不少锅233

杂题选讲

图染色问题相关？

WC的官方题解

如果有啥忘了发也懒得管了。